In network communication, a router is typically coupled to a plurality of other routers through a plurality of network interfaces and can forward traffic to networks or sub-networks. Consequently, the router needs to maintain forwarding information, such as network address prefixes, for all sub-networks and interfaces in a database, known as a Forwarding Information Base (FIB).
Upon receiving a packet, the router performs a network address lookup. The lookup process finds the longest match between the destination address of the packet and a network address prefix and determines the corresponding outgoing interface. Hence, storing and accessing such information efficiently and intelligently can improve the lookup process, and thereby one of the most challenging problems in today's networking paradigm.
Trie lookup is one of the most popular network address lookup techniques used in a router. A trie is a tree data structure, wherein the position of a node in the tree represents a corresponding key. Particularly for representing network address prefixes in a FIB, a node in a trie represents a longest prefix match up to the position of the node.
In a traditional layer 3 router, different algorithms may be used for Internet Protocol (IP) lookup and Ethernet lookup. Typically, hashing is used for Ethernet lookup, and multi-bit trie is used for IP lookup. Memory space is statically provisioned among Ethernet hash tables and IP Forwarding Information Base (FIB) with memory space statically partitioned according to an expected usage ratio.
For data center (DC) and cloud applications, tera bit per second (Tb/s) IP and Ethernet lookups are required for both Top of Rack (TOR) switches and line cards of core switches, whereas a large amount of host routes may be leaked due to virtual machine migration. In addition, low latency may be important for these applications. Such requirements present a unique set of challenges that have not been addressed by lookup algorithms developed for traditional layer 3 router markets.